/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-02-20
 * Time: 0:41
 */
public class test3 {
    /**
     * 字符串相乘 （优化版本）
     */

    public String multiply(String num1, String num2) {
        // 先无进位相乘，然后相加，再处理进位
        int m = num1.length();
        int n = num2.length();

        char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();
        int[] tmp = new int[m+n-1];

        // 无进位相乘，然后相加
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                tmp[i+j] += (n1[i]-'0') * (n2[j]-'0');
            }
        }

        // 处理进位
        int cur = 0;
        int t = 0;
        StringBuffer ret = new StringBuffer();
        while(cur<m+n-1 || t!=0){
            if(cur<m+n-1){
                t+=tmp[cur++];
            }
            ret.append((char)((char)(t%10)+'0'));
            t/=10;
        }

        // 处理前导0
        while(ret.length()>1 && ret.charAt(ret.length()-1)=='0'){
            ret.deleteCharAt(ret.length()-1);
        }
        return ret.reverse().toString();
    }
}
